#include<iostream>
#include<cstdlib>
#include<ctime>

using namespace std;

void swap(int &a,int &b)
{
	int t = a;
	a = b;
	b = t;
} 

void randomArr(int *arrP,int n)
{
	srand((int)time(0));
	for(int i=0;i<n;i++)
		arrP[i]=rand();
}

bool checkSort(int *arr,int n)
{
	for(int i=0;i<n-1;i++){
		if (arr[i]>arr[i+1])
			return false;
	}
	return true;
}


void printArr(int *arrP,int n)
{
    for (int i = 0; i < n; ++i)
        printf("%d ",*arrP++);
    printf("\n");
}


int main()
{
	int nums[] = {1,7,6,5,9,6,0};
//	int length = 200;
//	int nums[length];
//	randomArr(nums,length);
	int n = sizeof(nums)/sizeof(int);
	for (int j = 1;j<n;j++)
	{
//		int i = 1;
		int i = j;
		int cur = nums[i];
		int gap = 1;
		while(i>0 && cur < nums[i-gap])
        {
		    nums[i]=nums[i-gap];
            i-=gap;
        }
		nums[i]=cur;
		printArr(nums,n);

	}

	cout<<checkSort(nums,n)<<endl;
	for(int i=0;i<n;i++)
		printf("%d ",nums[i]);
	printf("\n");
}
